//正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
//
// 
//
// 
// 注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/ 
//
// Related Topics 字符串 动态规划 回溯 👍 93 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-03-29 23:52:35
 * @description LCR 085.括号生成
 */
public class IDBivT{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 IDBivT fun=new IDBivT();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	List<String> res=new ArrayList<>();

	public List<String> generateParenthesis(int n) {
		dfs(new StringBuilder(),n,0,0);
		return res;
    }
	private void dfs(StringBuilder sb,int n,int l,int r){
		if(sb.length()==n*2){
			res.add(sb.toString());
		}
		if(l<n){
			sb.append("(");
			dfs(sb,n,l+1,r);
			sb.deleteCharAt(sb.length()-1);
		}
		if(r<l){
			sb.append(")");
			dfs(sb,n,l,r+1);
			sb.deleteCharAt(sb.length()-1);
		}
	}

	/*所有的组合都可以写成(a)b的形式，先求a的组合，再求n-a-i的组合得到b的组合，然后拼接
	 * 递归的过程中保存方便再次计算
	 * cache就相当于n个括号可能的情况*/
	ArrayList[] cache=new ArrayList[100];
	private List<String> generateParenthesis1(int n){
		return generate(n);
	}
	private List<String>generate(int n){
		if(cache[n]!=null){
			return cache[n];
		}
		ArrayList<String> res = new ArrayList<>();
		if(n==0){
			res.add("");
		}else{
			for (int i = 0; i < n; i++) {
				for (String l : generate(i)) {
					for (String r : generate(n - i - 1)) {
						res.add("("+l+")"+r);
					}
				}
			}
		}
		cache[n]=res;
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
